package com.algrithom.unionfind;

import java.util.Arrays;

import com.common.model.UnionFind;

/**
 * 685. 冗余连接 II
 * 
 * @author think
 */
public class Solution6 {
    
    public static void main(String[] args){
        Solution6 solution6 = new Solution6();
        int[][] edges = new int[][]{{1,2},{1,3},{2,3}};
        System.out.println(Arrays.toString(solution6.findRedundantDirectedConnection(edges)));
    }
    
    public int[] findRedundantDirectedConnection(int[][] edges){
        int nodesCount = edges.length;
        UnionFind uf = new UnionFind(nodesCount + 1);
        int[] parent = new int[nodesCount + 1];
        for (int i = 1; i <= nodesCount; ++i) {
            parent[i] = i;
        }
        int conflict = -1;
        int cycle = -1;
        for (int i = 0; i < nodesCount; ++i) {
            int[] edge = edges[i];
            int node1 = edge[0];
            int node2 = edge[1];
            if (parent[node2] != node2) {
                conflict = i;
            } else {
                parent[node2] = node1;
                if (uf.find(node1) == uf.find(node2)) {
                    cycle = i;
                } else {
                    uf.union(node1,node2);
                }
            }
        }
        if (conflict < 0) {
            // 只有环 + 环&链（每个节点都只有一个父节点）
            return new int[]{edges[cycle][0],edges[cycle][1]};
        } else {
            // 环+环&链（有某个节点有大于或等于2两父节点）
            int[] conflictEdge = edges[conflict];
            if (cycle >= 0) {
                return new int[]{parent[conflictEdge[1]],conflictEdge[1]};
            } else {
                return new int[]{conflictEdge[0],conflictEdge[1]};
            }
        }
    }
}